/*
 * @lc app=leetcode id=279 lang=cpp
 *
 * [279] Perfect Squares
 */
class Solution {
public:
    int numSquares(int n) {
        vector<int> mark(100);
        for (int i=1; i*i <= n; i++) {
            mark.push_back(i*i);
        }

        vector<int> v(n+1, 0);
        v[0] = 0;
        v[1] = 1;
        for (int i=2; i<=n; i++) {
            v[i] = v[i-1]+1;
            for (auto m : mark) {
                if (i < m) {
                    break;
                }
                if (v[i] > v[i-m]+1) {
                    v[i] = v[i-m]+1;
                }
            }
        }
        return v[n];
    }
};

